package org.hhchat.leetcode.tree;

import org.hhchat.leetcode.dataStruct.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by hh23485 on 2017/8/22.
 */
public class code235_easy {
    static class Solution {
        List<TreeNode> lista;
        List<TreeNode> listb;

        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            lista = new ArrayList<>();
            listb = new ArrayList<>();
            if(search(lista,root,p)!=null && search(listb,root,q)!=null){
                for(int i=0;i<lista.size()&&i<listb.size();i++) {
                    if(lista.get(i).val==listb.get(i).val && (i==lista.size()-1||i==listb.size()-1||lista.get(i+1)!=listb.get(i+1))){
                        return lista.get(i);
                    }
                }
            }
            return null;
        }

        public TreeNode search(List<TreeNode> list, TreeNode root, TreeNode p) {
            if (root == null) {
                return null;
            }
            list.add(root);
            if (root.val == p.val) {
                return p;
            } else {
                if(root.left!=null) {
                    TreeNode result = search(list, root.left, p);
                    if (result != null) {
                        return result;
                    }
                }
                if(root.right!=null){
                    TreeNode result = search(list, root.right, p);
                    if (result != null) {
                        return result;
                    }
                }
            }
            list.remove(list.size() - 1);
            return null;
        }

    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(6);
        TreeNode l1 = new TreeNode(2);
        TreeNode l21=new TreeNode(0);
        TreeNode l22=new TreeNode(4);
        TreeNode l33=new TreeNode(3);
        TreeNode l34=new TreeNode(5);
        TreeNode r1=new TreeNode(8);
        TreeNode r21=new TreeNode(7);
        TreeNode r22=new TreeNode(9);
        root.left = l1;
        root.right = r1;
        l1.left = l21;
        l1.right=l22;
        l22.left=l33;
        l22.right=l34;
        r1.left =r21;
        r1.right=r22;
        Solution solution = new Solution();
        System.out.println(solution.lowestCommonAncestor(root,l21,r22).val);
    }
}

/**
 * 日了狗了 - - 讨论区的3行代码，然后才发现是二叉查找树。。。
 */

//public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//    while ((root.val - p.val) * (root.val - q.val) > 0)
//        root = p.val < root.val ? root.left : root.right;
//    return root;
//}